package com.peng.leetcode.sort;

/**
 * MergeSort
 *
 * @author: lupeng6
 * @create: 2020/12/10 20:45
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {9, 7, 5, 6, 4, 8, 1, 2, 3};
        new Solution().sort(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }

    static class Solution {
        public void sort(int[] arr) {
            int start = 0, end = arr.length - 1;
            this.sort(arr, start, end);
        }

        public void sort(int[] arr, int start, int end) {
            if (start >= end) {
                return;
            }
            int mid = (start + end) / 2;
            this.sort(arr, start, mid);
            this.sort(arr, mid + 1, end);
            this.marge(arr, start, mid, end);
        }


        private void marge(int[] arr, int left, int center, int right) {
            int[] mergeArr = new int[arr.length];
            int i = left;
            int j = center + 1;

            int mergeArrIndex = left;
            while (i <= center && j <= right) {
                if (arr[i] > arr[j]) {
                    mergeArr[mergeArrIndex++] = arr[j++];
                } else {
                    mergeArr[mergeArrIndex++] = arr[i++];
                }
            }

            while (i <= center) {
                mergeArr[mergeArrIndex++] = arr[i++];
            }
            while (j <= right) {
                mergeArr[mergeArrIndex++] = arr[j++];
            }

            int tempIndex = left;
            while (tempIndex <= right) {
                arr[tempIndex] = mergeArr[tempIndex];
                tempIndex++;
            }
        }
    }

}
